package Demo1;

import java.util.Arrays;

class demo1 {
    public int minNum = Integer.MAX_VALUE;
    public int n;
    public int[][] memory;

    public int minFallingPathSum(int[][] matrix) {
        n = matrix.length;
        memory = new int[n][n];
        for (int i = 0; i < n; i++)
            Arrays.fill(memory[i], Integer.MAX_VALUE);
        for (int i = 0; i < n; i++) {
            minNum = Math.min(dfs(matrix, 0, i), minNum);
        }
        return minNum;
    }

    public int dfs(int[][] matrix, int i, int j) {
        if (i == n)
            return 0;
        if (j < 0 || j >= n)
            return Integer.MAX_VALUE;

        if (memory[i][j] != Integer.MAX_VALUE)
            return memory[i][j];
        int left = dfs(matrix, i + 1, j - 1);
        int middle = dfs(matrix, i + 1, j);
        int right = dfs(matrix, i + 1, j + 1);

        memory[i][j] = Math.min(Math.min(left, middle), right) + matrix[i][j];
        return memory[i][j];
    }
}
